package org.gzc.sort;

import java.util.Arrays;

/**
 * @Description: 希尔排序
 * @Author: guozongchao
 * @Date: 2020/8/8 23:35
 */
public class ShellSort implements SortStrategy{
    @Override
    public void sort(int[] array) {
        //把数组元素按照下标的一定增量(gap)分组，直至增量为1，所有的元素恰好分为一组
        for (int gap=array.length/2;gap>=1;gap=gap/2) {
            //对分好的每一个组的所有元素进行直接插入排序
            //直接插入排序，假设第一个元素为有序序列，从第二个元素开始为无序序列，从第二元素开始，比较并插入到有序序列中
            //gap刚好是第一组的第二个元素的下标，随着i的递增，分别对应第二组、第三组....的第二个元素下标
            for (int i = gap; i < array.length; i++) {
                int insertVal = array[i];   //临时存放需要插入的值
                int insertIndex=i-gap;    //由于元素按照增加gap递增，因此前一个元素的下标为i-gap
                while (insertIndex >= 0 && insertVal < array[insertIndex]) {
                    //如果插入值比前面元素的值小，则前面的元素后移一个位置
                    array[insertIndex + gap] = array[insertIndex];
                    insertIndex-=gap;
                }
                //优化：如果发生了移动，则执行插入，没有移动则不需要进行对于的插入操作
                if (insertIndex + gap != i) {
                    array[insertIndex+gap]=insertVal;
                }
            }
            //System.out.println("gap="+gap+"，排序后："+ Arrays.toString(array));
        }
    }
}
